package tree.structure.huffman;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author: 26233
 * @create: 2022-07-25 17:43:13
 * @Description
 *
 * 哈夫曼编码：将哈夫曼树的叶子节点数据进行01编码，假设左路径表示0，右路径表示1
 *  1. 作用：
 *      a. 减少原始数据的存储空间，相比较使用定长的编码
 *      b. 前缀编码，即不同数据的前缀一定是不相同的
 *
 **/

public class HuffmanCode {

    public Map<Integer, String> huffmanCodeFromTree(HuffmanTree huffmanTree){
        Map<Integer, String> result = new HashMap<>();
        travelHuffmanTree(result, huffmanTree.getRoot(), new StringBuilder());

        return result;
    }

    public void travelHuffmanTree(Map<Integer, String> result, HuffmanTreeNode curNode, StringBuilder curResult){
        if(curNode.getLeft() == null && curNode.getRight() == null) {
            result.put(curNode.getWeight(), curResult.toString());
            curResult.deleteCharAt(curResult.length() - 1);
            return;
        }
        if(curNode.getLeft() != null) {
            curResult.append("0");
            travelHuffmanTree(result, curNode.getLeft(), curResult);
        }
        if(curNode.getRight() != null) {
            curResult.append("1");
            travelHuffmanTree(result, curNode.getRight(), curResult);
        }
        if(curResult.length() > 0){
            curResult.deleteCharAt(curResult.length() - 1);
        }
    }

    public static void main(String[] args) {
        int[] weights = new int[]{2, 3, 6, 7, 10, 19, 21, 32};
        List<HuffmanTreeNode> collect =
                Arrays.stream(weights)
                        .mapToObj(HuffmanTreeNode::genNode)
                        .sorted(Comparator.comparingInt(HuffmanTreeNode::getWeight))
                        .collect(Collectors.toList());

        HuffmanTree huffmanTree = new HuffmanTree();
        huffmanTree.genHuffmanTree(collect);

        Map<Integer, String> integerStringMap = new HuffmanCode().huffmanCodeFromTree(huffmanTree);
        System.out.println("integerStringMap = " + integerStringMap);

        // integerStringMap = {32=11, 2=10000, 19=00, 3=10001, 21=01, 6=1001, 7=1010, 10=1011}

    }

}
